package 二叉树相关问题.中度题;

import java.util.LinkedList;
import java.util.List;

public class 二叉树和为某一值的路径 {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> lists = new LinkedList<>();
        if (root==null)
            return lists;
        dfs(lists,root,target,new LinkedList<Integer>());
        return lists;
    }
    private void dfs(List<List<Integer>> lists, TreeNode root,int target,List<Integer> list) {
        if (root==null)
            return;
        if (root.left==null && root.right==null && target==0){
            lists.add(new LinkedList<>(list));
            return;
        }
        list.add(root.val);
        dfs(lists,root.right,target-root.val,list);
        dfs(lists,root.left,target-root.val,list);
        list.remove(list.size()-1);
    }
}
